package com.sicheng.lc.周赛.分类.思维.数论;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/1 20:49
 */
public class 查找给定哈希值的子串 {


    //https://leetcode.cn/problems/find-substring-with-given-hash-value/
    // hash(s,p,m)
    // p^k % m
    long[] mod;

    void init(int p, int m, int k) {
        mod = new long[k + 1];
        mod[0] = 1 % m;
        for (int i = 1; i <= k; i++) {
            mod[i] = mod[i - 1] * (p % m) % m;
        }
    }

    public String subStrHash(String s, int p, int m, int k, int hashValue) {
        init(p, m, k);
        long last;
        int r = s.length() - 1;
        int l = s.length() - k;
        long hash = 0;
        for (int i = l; i <= r; i++) {
            hash = (hash + (s.charAt(i) - 'a' + 1) * mod[i - l] % m) % m;
        }
        long newHash;
        int i = l, j = r;
        while (l > 0) {
            last = (s.charAt(r) - 'a' + 1) * mod[k - 1] % m;
            r--;
            l--;
            newHash = ((hash - last + m) % m * p % m + (s.charAt(l) - 'a' + 1)) % m;
            hash = newHash;
            if (hash == hashValue) {
                i = l;
                j = r;
            }
        }
        return s.substring(i, j + 1);
    }

    public static void main(String[] args) {
        查找给定哈希值的子串 s = new 查找给定哈希值的子串();
        System.out.println(s.subStrHash("leetcode", 7, 20, 2, 0));
    }

}
